export interface IData {
    key:number,
}

export interface INode<T>{
    root:INode<T> | null,
    left:INode<T> | null,
    right:INode<T> | null,
    data: T,
}

export class Node<T extends IData>  implements INode<T>{
    root:INode<T> | null;
    left:INode<T> | null;
    right:INode<T> | null;
    data:T;
    constructor(data:T) {
        this.data = data;
        this.root = this;
    }
}


export class TBinaryTreeNode<T extends IData>{

    root:INode<T>;

    public insert(data:T){
        const newNode = new Node(data);
        if(!this.root){
            this.root = newNode;
        }else{
            this.insertNode(this.root, newNode);
        }
    }

    public inForEach(callback:(d:T) => T){
        let listNodeData:T[] = [];
        this.inForEachNode(this.root,listNodeData, callback);
        return listNodeData;
    }

    public centerForEach(callback:(d:T) => T){
        let listNodeData:T[] = [];
        this.centerForEachNode(this.root,listNodeData, callback);
        return listNodeData;
    }

    public afterForEach(callback:(d:T) => T){
        let listNodeData:T[] = [];
        this.afterForEachNode(this.root,listNodeData, callback);
        return listNodeData;
    }

    public find(key:number){
        if(!key)return null;
        return this.findNode(this.root, key);
    }

    public remove(key:number){
        if(!key) return null;
        return this.removeNode(this.root, key);
    }


    private insertNode(root: INode<T> | null, newNode: INode<T> | null) {
        if (!root) return;
        if (!newNode) return;
        if(newNode.data.key < root.data.key){
            if(!root.left){
                root.left = newNode;
            }else{
                this.insertNode(root.left, newNode);
            }
        }else{
            if(!root.right){
                root.right = newNode;
            }else{
                this.insertNode(root.right, newNode);
            }
        }
    }

    private inForEachNode(root: INode<T> | null, listNodeData: T[], callback: (v:T) => T) {
        if(!!root){
            listNodeData.push(callback(root.data));
            this.inForEachNode(root.left,listNodeData,callback);
            this.inForEachNode(root.right,listNodeData,callback);
        }
    }

    private centerForEachNode(root: INode<T> | null, listNodeData: T[], callback: (d: T) => T) {
        if(!!root){
            this.inForEachNode(root.left,listNodeData,callback);
            listNodeData.push(callback(root.data));
            this.inForEachNode(root.right,listNodeData,callback);
        }
    }

    private afterForEachNode(root: INode<T> | null, listNodeData: T[], callback: (d: T) => T) {
        if(!!root){
            this.inForEachNode(root.left,listNodeData,callback);
            this.inForEachNode(root.right,listNodeData,callback);
            listNodeData.push(callback(root.data));
        }
    }

    private findNode(root: INode<T> | null, key: number):INode<T> | null {
        if(!root) return  null;
        if(root.data.key === key){
            return  root;
        }else if(key < root.data.key){
            return this.findNode(root.left,key);
        }else if(key > root.data.key){
            return  this.findNode(root.right,key);
        }
        return null;
    }

    private removeNode(root: INode<T> | null, key: number): INode<T> | null{
        if(!root) return  null;
        if(key < root.data.key){
            root.left = this.removeNode(root.left, key);
            console.log(root, ".......")
            return  root
        }else if(key > root.data.key){
            root.right = this.removeNode(root.right, key);
            return  root
        }else{
               if(!root.left && !root.right) return null;
               if(!root.left) return  root.right;
               if(!root.right) return root.left;
               if(!!root.left && !!root.right){
                   let newNode = this.getMinNode(root.right, root.data.key);
                   if(newNode){
                       root.data = newNode.data;
                       root.right = this.removeNode(root.right, newNode.data.key);
                       return  root;
                   }else{
                       return  null;
                   }
               }else{
                   return  null;
               }
        }
    }

    private getMinNode(root: INode<T>, key: number):INode<T> | null {
        return root ? root.left ? this.findNode(root.left, key) : root : null;
    }
}
